package com.ly.algorithm.leetcode.BST;


import java.util.*;

/**
 * @Classname Problem538
 * @Description
 * 给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
 *
 *  
 *
 * 例如：
 *
 * 输入: 原始二叉搜索树:
 *               5
 *             /   \
 *            2     13
 *
 * 输出: 转换为累加树:
 *              18
 *             /   \
 *           20     13
 *
 * @Date 2020/9/21 17:33
 * @Author 冷心影翼
 */
public class Problem538 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(2);
        TreeNode left = new TreeNode(1);
        TreeNode right = new TreeNode(3);
        root.left = left;
        root.right = right;
        Solution538 solution538 = new Solution538();
//        solution538.convertBST(root);
        solution538.convertBST2(root);
        System.out.println(root.left.val);
    }
}

class Solution538 {
    public TreeNode convertBST(TreeNode root) {
        if(root == null) {
            return null;
        }
        Deque<TreeNode> queue = new ArrayDeque<> ();
        List<Integer> list = new ArrayList<>();
        queue.add(root);
        while (queue.size()>0) {
            TreeNode pop = queue.pop();
            list.add(pop.val);
            if(pop.left != null)
                queue.add(pop.left);
            if(pop.right != null)
                queue.add(pop.right);
        }
        Integer[] arr = new Integer[list.size()];
        Arrays.sort(list.toArray(arr));
        preOrder(arr,root);
        return root;
    }

    public void preOrder(Integer[] arr, TreeNode treeNode) {
        if(treeNode == null) {
            return;
        }
        int val = treeNode.val;
        for(int i=0;i<arr.length;i++) {
            if(val < arr[i]) {
                treeNode.val += arr[i];
            }
        }
        preOrder(arr,treeNode.left);
        preOrder(arr,treeNode.right);
    }

    public TreeNode convertBST2(TreeNode root) {
        midOrder(root);
        return root;
    }

    private int sum = 0;

    public void midOrder(TreeNode root) {
        if(root == null) {
            return;
        }
        midOrder(root.right);
        sum += root.val;
        root.val = sum;
        midOrder(root.left);
    }
}